package ext;

import def.TreeNode;

/**
 * 最长同色路径
 */
public class LongestPath {
    int ans = 0;

    public int findPath(TreeNode root) {
        traversal(root, 0);
        return ans;
    }

    public void traversal(TreeNode root, int curLen) {
        if (root == null)
            return;

        curLen++;
        if (curLen > ans)
            ans = curLen;

        if (null != root.left)
            traversal(root.left, root.left.val == root.val ? curLen : 0);

        if (null != root.right)
            traversal(root.right, root.right.val == root.val ? curLen : 0);

    }

    public static void main(String[] args) {

        TreeNode n1 = new TreeNode(0);
        TreeNode n2 = new TreeNode(1);
        TreeNode n3 = new TreeNode(1);
        TreeNode n4 = new TreeNode(1);
        TreeNode n5 = new TreeNode(1);
        TreeNode n6 = new TreeNode(1);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.right = n6;

        n6.right = new TreeNode(0);

        LongestPath sol = new LongestPath();
        System.out.println(sol.findPath(n1));
    }
}